package 我的Java学习_算法基础.day_08;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @date 2021/8/23 - 08 - 23 - 14:04
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _124_区间调度问题 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] begin = new int[n];
        int[] end = new int[n];
        for(int i =0;i<n;i++){
            begin[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            end[i] = sc.nextInt();
        }
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(begin[i],end[i]);
        }
        Arrays.sort(jobs); //根据结束时间排序，结束早的在前
        int count =findJob(jobs);
        System.out.println(count);
    }

    /**
     * 在所有工作中，干尽可能多的工作
     * 干一件工作，继续做完，所有工作区间不能重合，
     * 哪怕是一件工作结束时另一个工作刚开始，也不行
     * 思路：每次找最早结束的工作，
     * 且这个工作的开始时间在上次所选工作结束时间之后
     * @param jobs
     * @return
     */
    private static int findJob(Job[] jobs){
        int count = 1;
        int end = jobs[0].end;
        for (int i = 0; i < jobs.length; i++) {
            if(jobs[i].begin>end){
                count++;
                end = jobs[i].end;
            }
        }
        return count;
    }

    /**
     * 将每件工作根据起始时间和结束时间封装成对象
     */
    private static class Job implements Comparable<Job>{
        int begin;
        int end;
        public Job(int begin,int end){
            this.begin = begin;
            this.end = end;
        }
        //根据结束时间排序，结束早的在前，结束时间相同时，开始时间早的在前
        @Override
        public int compareTo(Job o) {
            int t = this.end - o.end;
            if(t==0){
                return this.begin - o.begin;
            }else{
                return t;
            }
        }
    }
}
